package com.xinheyun.demo.leetcode;

import java.util.ArrayList;

/**
 * @description: TODO
 * @author: Sarah
 * @modified By: Sarah
 * @date: Created in 2021/8/20 14:59
 * @version:v1.0
 */
//硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
//
//    示例1:
//
//    输入: n = 5
//    输出：2
//    解释: 有两种方式可以凑成总金额:
//    5=5
//    5=1+1+1+1+1
//    示例2:
//
//    输入: n = 10
//    输出：4
//    解释: 有四种方式可以凑成总金额:
//    10=10
//    10=5+5
//    10=5+1+1+1+1+1
//    10=1+1+1+1+1+1+1+1+1+1
//    1/5/10/25
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/coin-lcci
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class test2259 {

    public static void main(String[] args) {
        test2259 test2259 = new test2259();
        System.out.println(test2259.waysToChange(10777));
    }


    static final int MOD = 1000000007;
    int[] coins = {25, 10, 5, 1};

    public int waysToChange(int n) {
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int c = 0; c < 4; ++c) {
            int coin = coins[c];
            for (int i = coin; i <= n; ++i) {
                f[i] = (f[i] + f[i - coin]) % MOD;
            }
        }
        return f[n];
    }
//    给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
//
//    nums[0] = 0
//    nums[1] = 1
//    当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
//    当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
//    返回生成数组 nums 中的 最大 值。
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/get-maximum-in-generated-array
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


    static int N = 110;
    static int[] nums = new int[N];

    static {
        nums[0] = 0;
        nums[1] = 1;
        for (int i = 0; i < N; i++) {
            if (2 * i < N) {
                nums[2 * i] = nums[i];
            }
            if (2 * i + 1 < N) {
                nums[2 * i + 1] = nums[i] + nums[i + 1];
            }
        }
        for (int i = 0, max = 0; i < N; i++) {
            nums[i] = max = Math.max(max, nums[i]);
        }
    }

    public int getMaximumGenerated(int n) {
        return nums[n];
    }


}
